package pers.qianyu.month_202101.date_20210103;

import java.util.*;

/**
 * 576. 出界的路径数
 * https://leetcode-cn.com/problems/out-of-boundary-paths/
 *
 * @author mizzle rain
 * @date 2020-12-31 15:54
 */
public class FindPaths {
    // memo[i][j][k] 表示走到位置坐标为 (i, j) ，并且还剩 k 步的时候，有几种方案
    private int[][][] memo;
    private int[][] direction = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    private final int mod = 1000000007;

    public int findPaths(int m, int n, int N, int i, int j) {
        memo = new int[m][n][N + 1];
        for (int[][] arrs : memo) {
            for (int[] arr : arrs) {
                Arrays.fill(arr, -1);
            }
        }
        return dp(m, n, i, j, N);
    }

    private int dp(int m, int n, int i, int j, int k) {
        if (memo[i][j][k] != -1) {
            return memo[i][j][k];
        }
        if (k == 0) {
            return 0;
        }
        memo[i][j][k] = 0;
        for (int[] d : direction) {
            int x = d[0] + i, y = j + d[1];
            if (x < 0 || y < 0 || x == m || y == n) {
                memo[i][j][k] += 1;
            } else {
                memo[i][j][k] += dp(m, n, x, y, k - 1);
            }
            memo[i][j][k] %= mod;
        }
        return memo[i][j][k];
    }
}
